1 线性表课后编程题

01.从顺序表中删除具有最小值的元素（假设唯一）并由函数返回被删元素的值。空出的位置由最后一个元素填补，若顺序表为空，则显示出错信息并退出运行。

typedef int datatype
typedef struct node_st{
	datatype *data;
	int last;
}sqlist;

datatype sqlist_mindel(sqlist *L){
	if(L->last==0)
		return -1;
	datatype data;
	data = L->data[0];
	int pos = 0,i;
	for(i=1;i<L->last;i++){
		if(L->data[i]<data){
			data = L->data[i];
			pos = i;
		}
	}
	L->data[pos]=L->data[L->last-1]; //顺序表末尾减一
	L->last--;
	return data;
}

01.设计一个递归算法，删除不带头结点的单链表L中所有值为×的结点

typedef int datatype;
typedef struct node_st{
	typedef *data;
	struct node_st *next;
}llist;

bool del_x(llist* L,datatype data){
	if(L==NULL)
		return true;
	if(L->data==data){
		llist *tmp;
		tmp = L;
		L=L->next;
		free(tmp);
		del_x(L,datatype data);
	}else{
		del_x(L->next,datatype data);
	}
}

02.设置一个高效的算法，将顺序表L的所有元素逆置，算法复杂度O(1)

typedef int datatype
typedef struct node_st{
	datatype *data;
	int last;
}sqlist;

void reverse(sqlist *L){
	datatype tmp;
	for(int i =0;i<L->last/2;i++){
		tmp=L->data[i];
		L->data[i]=L->data[L->last-i-1];
		L->data[L->last-i-1]=tmp;
	}
}

03.带头节点的点链表L中，删除所有值为X的节点，X不唯一

typedef int datatype;
typedef struct node_st{
	datatype data;
	struct node_st *next;
}llist;

int del_x(llist *L,datatype data){
	struct llist *p = L,*tmp;
	while(p->next!=NULL){
		if((p->next)->data==data){
			tmp=p->next;
			p->next=tmp->next;
			free(tmp);
			p=p->next;
		}
		p=p->next;
	}
	return 0;
}

04、设L是带头节点的单链表，反向输出值

typedef int datatype;
typedef struct node_st{
	datatype data;
	struct node_st *next;
}llist;

void reversel(llist*L){
	llist *prev,*cur=L->next,*next;
	while(cur!=NULL){
		next = cur->next;
		cur->next=prev;
		prev=cur;
		cur=next;
	}
	while(prev!=null){
		printf("%d->",prev->data);
		prev=prev->next;
	}
}

05.对长度为n的顺序表L，编写一个时间复杂度为O(n)、空间复杂度为0（1)的算法，该算法删除线性表中所有值为x的数据元素

typedef int datatype
typedef struct node_st{
	datatype *data;
	int last;
}sqlist;
//k是记录不等于data的值的
void del_x(sqlist *L,datatype data){
	int k=0,i;
	for(i=0;i<L.last;i++){
		if(L->data[i]!=data){
			L->data[k]=L->data[i];
			k++;
		}
	}
	L->last=k;
}